class Node{
    constructor(key, value){
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}
class NodeTable{
    headNode = null;
    tailNode = null;
    // 添加到目标的上一个节点
    addToPrev(node, target){
        const prev = target.prev;
        target.prev = node;
        prev.next = node;
        node.next = target;
        if(prev){
            node.prev = prev;
        }else{
            this.headNode = node;
        }
    }
    // 添加到目标的下一个节点
    addToNext(node, target){
        const next = target.next;
        target.next = node;
        next.prev = node;
        node.prev = target;
        if(next){
            node.next = next;
        }else{
            this.tailNode = node;
        }
    }
    addToHead(node){
        if(!this.headNode){  
            this.headNode = node;
            this.tailNode = node;
        }else{
            const head = this.headNode;
            this.headNode = node;
            node.next = head;
            head.prev = node;
        }
    }
    addToTail(node){
        if(!this.tailNode){
            this.tailNode = node;
            this.headNode = node;
        }else{
            const tail = this.tailNode;
            this.tailNode = node;
            node.prev = tail;
            tail.next = node;
        }
    }
    delete(node){
        const prev = node.prev;
        const next = node.next;
        if(prev){
            prev.next = next;
        }else{
            this.headNode = next;
        }
        if(next){
            next.prev = prev;
        }else{
            this.tailNode = prev;
        }
    }
}

class LRUCache{
    max = 0;
    cacheData = new Map();
    constructor(max){
        this.max = max;
        this.nodeTable = new NodeTable();
    }
    put(key, value){
        if(this.cacheData.has(key)){
            const node = this.cacheData.get(key);
            node.value = value;
            this.nodeTable.delete(node);
            this.nodeTable.addToTail(node);
        }else{
            const node = new Node(key, value);
            // 检查是否超出容量
            if(this.cacheData.size >= this.max){
                // 删除最老的节点（头节点）
                const oldestNode = this.nodeTable.headNode;
                this.nodeTable.delete(oldestNode);
                this.cacheData.delete(oldestNode.key);
            }
            // 添加新节点
            this.cacheData.set(key, node);
            this.nodeTable.addToTail(node);
        }
    }
    get(key){
        if(!this.cacheData.has(key)){
            return -1;
        }
        const node = this.cacheData.get(key);
        this.nodeTable.delete(node);
        this.nodeTable.addToTail(node);
        return node.value;
    }
}
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
console.log(cache.get(2));       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
console.log(cache.get(1));       // 返回 -1 (未找到)
console.log(cache.get(3));       // 返回  3
console.log(cache.get(4));       // 返回  4